package code.DP.最长回文子串;

class Solution {
	public static void main(String[] args) {
		Solution solution = new Solution();
		String abcddcba = solution.longestPalindromeDP("abcddcba");
		System.out.println(abcddcba);
	}

	public boolean isPalindromic(String s) {
		int len = s.length();
		for (int i = 0; i < len / 2; i++) {
			if (s.charAt(i) != s.charAt(len - i - 1)) {
				return false;
			}
		}
		return true;
	}

	// 暴力解法
	public String longestPalindromeVo(String s) {
		String ans = "";
		int max = 0;
		int len = s.length();
		for (int i = 0; i < len; i++)
			for (int j = i + 1; j <= len; j++) {
				String test = s.substring(i, j);
				if (isPalindromic(test) && test.length() > max) {
					ans = s.substring(i, j);
					max = Math.max(max, ans.length());
				}
			}
		return ans;
	}

	public String longestPalindromeDP(String s) {
		int length = s.length();
		if (length < 2) {
			return s;
		}
		boolean[][] dp = new boolean[length][length];
		int start = 0;
		int end = 0;
		int maxLen = 1;

		for (int i = 1; i < length; i++) {
			for (int j = 0; j < i; j++) {
				if (s.charAt(i) == s.charAt(j) && (i - j < 2 || dp[j + 1][i - 1])) {
					dp[j][i] = true;
					if (i - j + 1 > maxLen) {
						start = j;
						end = i;
						maxLen = j - i + 1;
					}
				}
			}
		}

		return s.substring(start, end + 1);
	}

	public String longestPalindromeET(String s) {
		if (s == null || s.length() < 1) return "";
		int start = 0, end = 0;
		for (int i = 0; i < s.length(); i++) {
			int len1 = expandAroundCenter(s, i, i);
			int len2 = expandAroundCenter(s, i, i + 1);
			int len = Math.max(len1, len2);
			if (len > end - start) {
				start = i - (len - 1) / 2;
				end = i + len / 2;
			}
		}
		return s.substring(start, end + 1);
	}

	private int expandAroundCenter(String s, int left, int right) {
		int L = left, R = right;
		while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
			L--;
			R++;
		}
		return R - L - 1;
	}
}
